Redundant Arrays of Inexpensive Disks (RAID) systems are now being offered commercially as cost effective mass storage providing reliable and continuous service to a host computer or network file server. These arrays of hard disk drives are managed by a (hardware or software) controller to appear to the host system as a single drive having a large contiguous set of "logical" data blocks. A typical input/output (I/O) request from the host computer is serviced by transfering the appropriate data in the proper order from one or more of the physical drives in the array. The goal is to select the physical array structure and to map the logical data blocks to the physical drives in a manner that provides fault tolerance to drive failures and that facilitates efficient data transfer rates. Redundant data or parity data is used to recover data that is lost when a drive fails.
Several storage formats, termed "RAID levels", for byte or block striping data across the drives have become popular--e.g. RAID-4 (block striped with or without a parity drive), RAID-1 (mirrored block data), RAID-3 (byte striped with a parity drive), and RAID-5 (block striped with parity blocks distributed on all drives). See "A Case for Redundant Arrays of Inexpensive Disks (RAID)", by David A. Patterson et. al., University of California Berkeley, Report No. UCB/CSD 87/391, December 1987. Data security require and typical data access characteristics determines which of these formats is most suitable for a particular application environment. For example, an environment requiring fault tolerance to drive failure, but with typical accesses consisting of large blocks of contiguous data may be better supported by RAID-3, while one with typical accesses consisting of random small blocks of data may be better supported by RAID-5.
In handling single data access requests from a host system, current RAID control systems incur significant added latency due to the drive array access methods used, and, in handling multiple queued data access requests, they incur reduced throughput due to the scheduling methods used or even the lack of scheduling. The present invention includes innovations to optimize access latency and throughput for single or multiple queued access requests. Due to architectural design, current control systems also have limited, high cost, and complex methods for fault tolerance and expansion. The present invention introduces architectural innovations that reduce cost and complexity.